
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#include "guitarra.h"

#define MINIMO 0

/**
 * Faz a alocação dinâmica de uma matriz de inteiros
 *
 * m -> número de linhas da matriz
 * n -> número de colunas da matriz
 */
int ** alocaMatriz(int m, int n) {
	int **v;
	int   i;
	if (m < 1 || n < 1) {
		printf ("** Erro: Parametro invalido **\n");
		return (NULL);
	}

	v = (int **) calloc (m, sizeof(int *));
	if (v == NULL) {
		printf ("** Erro: Memoria Insuficiente **");
		return (NULL);
	}

	for ( i = 0; i < m; i++ ) {
		v[i] = (int*) calloc (n, sizeof(int));
		if (v[i] == NULL) {
			printf ("** Erro: Memoria Insuficiente **");
			return (NULL);
		}
	}
	return (v);
}

/**
 * Libera a memória alocada por uma matriz
 */
int **liberaMatriz(int **matriz, int n) {

	int i;
	for(i = 0; i < n-1; i ++) {
		free(matriz[i]);
	}
	free(matriz);
	return (NULL);

}
/**
 * Eleva o a base 'b' ao expoente 'e'
 * b -> base
 * e -> expoente
 */
long potencia(long b,long e) {
	long i =0;
	long r = 1;
	for(i = 0; i < e; i++) {
		r *= b;
	}
	return r;
}

/**
 * Faz o preenchimento da árvore com todas as possibilidades de solução para o problema
 * desconsiderando as regras de maior e menor volume.
 *
 * arvore -> árvore de soluções
 * posicao -> posição corrente da construção
 * numNiveis -> número de níveis da árvore
 * nivel -> nivel atual da construção
 * inicio -> posição corrente da construção
 * variacoes -> variações de volumes das músicas
 *
 */
void criarArvoreSolucoes(int *arvore, long posicao, int numNiveis, int nivel, int inicio, int *variacoes) {

	if(nivel == numNiveis) {
		return;
	}

	arvore[posicao] = inicio;

	int p = arvore[posicao];
	int v = variacoes[nivel];
	criarArvoreSolucoes(arvore,(posicao*2) + 1,numNiveis,nivel+1, p + v,variacoes);
	criarArvoreSolucoes(arvore,(posicao*2) + 2,numNiveis,nivel+1, p - v,variacoes);

}

/**
 * Verifica se o caminho até um determinado ponto da árvore é válido
 *
 * arvore -> arvore de possibilidades de volume das músicas
 * indice -> índice do elemento da árvore que se quer verificar
 * limite -> volume máximo que as músicas podem atingir
 */
int verificarCaminho(int *arvore, int indice, int limite) {

	if(indice == 0) {
		return 1;
	}

	if(arvore[indice] > limite || arvore[indice] < 0) {
		return 0;
	}

	int indiceSuperior = 0;
	int condicao = (indice % 2) == 0;
	if(condicao) {
		indiceSuperior = (indice - 2) / 2;
	} else {
		indiceSuperior = (indice - 1) / 2;
	}

	return verificarCaminho(arvore,indiceSuperior , limite);
}

/**
 * Verifica para cada item do último nível da árvore se o caminho percorrido é válido
 *
 * arvore -> arvore de possibilidades de volume das músicas
 * final -> vetor que indica se a sequencia até as últimas músicas é valida
 * numItens ->  total de itens na árvore
 * limite -> volume máximo que as músicas podem atingir
 */
void obterCaminhosValidos(int *arvore, int *final, int numItens, int inicioUltimoNivel, int limite) {

	int i,k;
	for(i = inicioUltimoNivel, k = 0; i < numItens; i++, k++) {
		int valor = verificarCaminho(arvore,i,limite);
		final[k] = valor;
	}
}

/**
 * Retorna maior volume para  última música a partir dos possíveis volumes finais
 * e dos valores finais que são válidos para o caso de teste
 *
 * arvore -> arvore de possibilidades de volume das músicas
 * final -> vetor que indica se a sequencia até as últimas músicas é valida
 * inicioUltimoNivel -> indice de início do último nível
 * numItens ->  total de itens na árvore
 */
int obterMaiorCaminho(int *arvore, int *final, int inicioUltimoNivel, int numItens) {

	int maior = -1;
	int i,k;
	for(i = inicioUltimoNivel, k = 0; i < numItens; i++, k++) {
		if(final[k]) {
			if (arvore[i] > maior) {
				maior = arvore[i];
			}
		}
	}
	return maior;
}

/**
 * Obtém o maior volume para a última música, pelo método força bruta
 *
 * casoTeste -> ponteiro para um caso de teste
 *
 *  retorna o maior volume da última música, ou -1 caso a sequencia das variaçõe leve sempre a um valor inválido de volume
 */
int volumeUltimaMusicaForcaBruta(PCasoTeste casoTeste) {


	int n = casoTeste->itemCasoTeste.numMusicas;
	int inicio = casoTeste->itemCasoTeste.volumeInicial;
	int maximo = casoTeste->itemCasoTeste.volumeLimite;
	int *variacoes = casoTeste->itemCasoTeste.variacoes;

	int itensArvore = potencia(2,n) - 1;
	int *arvore = (int *) malloc(sizeof(int)*itensArvore);
	criarArvoreSolucoes(arvore,0,n,0,inicio,variacoes);

	int indiceUltimoNivel = (itensArvore - 1) / 2;
	int itensUltimoNivel = (itensArvore+1)/2;
	int *finais = malloc(sizeof(int)*itensUltimoNivel);

	int i;
	for(i  = 0; i < itensUltimoNivel; i++)
		finais[i] = 0;

	obterCaminhosValidos(arvore,finais,itensArvore,indiceUltimoNivel,maximo);
	int maior = obterMaiorCaminho(arvore,finais,indiceUltimoNivel,itensArvore);

	free(arvore);
	free(finais);

	return maior;
}


/**
 * Método para determinar se dado um volume final e uma sequencia de variações é possível
 * chegar a um valor inicial dado com toda a sequencia passando por valores válidos.
 *
 * inicial -> valor inicial que se quer chegarl
 * volume -> volume a ser verificado
 * maximo -> valor máximo de volume que será considerado válido
 * indiceVariacoes -> índice da variação a ser verificado e em seguida subtraído e somado ao volume atual
 * memoria -> memoria da programação dinâmica, será utilizada para armazenar os valores inválidos de indice variacao com volume, evitando recálculos desncessários
 *
 * retorna o volume inicial caso o volume passado inicialmente seja válido para uma sequencia de músicas ou -1, caso não se possa chegar
 * ao volume final dado com toda a sequencia de músicas sendo válidas
 *
 */
int maiorVolumeValido(int inicial, int volume, int maximo, int indiceVariacoes, int *variacoes, int **memoria) {

	if(volume > maximo || volume < MINIMO) {
			return -1;
	}

	if (indiceVariacoes == 0 && volume == inicial) {
			return volume;
	}

	if (indiceVariacoes <= 0) {
			return -1;
	}



	int v = variacoes[--indiceVariacoes];

	if(memoria[volume][indiceVariacoes] == -1) return -1;

	int menos = maiorVolumeValido(inicial, volume - v, maximo,indiceVariacoes,variacoes, memoria);
	int mais = maiorVolumeValido(inicial, volume + v, maximo,indiceVariacoes,variacoes, memoria);

	memoria[volume][indiceVariacoes] = menos;
	memoria[volume][indiceVariacoes] = mais;

	if(menos >=0) {
		return menos;
	} else if(mais >= 0) {
		return mais;
	} else {
		return -1;
	}

}

/**
 * Obtém o maior volume para a última música, pelo método de programação dinâmica
 *
 * casoTeste -> ponteiro para um caso de teste
 *
 *  retorna o maior volume da última música, ou -1 caso a sequencia das variaçõe leve sempre a um valor inválido de volume
 */
int volumeUltimaMusicaDinamico(PCasoTeste casoTeste) {

	int n = casoTeste->itemCasoTeste.numMusicas;
	int inicio = casoTeste->itemCasoTeste.volumeInicial;
	int maximo = casoTeste->itemCasoTeste.volumeLimite;
	int *variacoes = casoTeste->itemCasoTeste.variacoes;
	int **memoria = alocaMatriz(maximo+1,n-1);

	int i,j;
	for(i = 0; i <= maximo; i++) {
		for(j = 0; j < n-1; j++) {
			memoria[i][j] = 0;
		}
	}


	for ( i = maximo; i > MINIMO; i--) {

		int r = maiorVolumeValido(inicio,i,maximo,n-1,variacoes,memoria);

		if(r >= 0) {
			liberaMatriz(memoria,maximo+1);
			return i;
		}

	}

	liberaMatriz(memoria,maximo+1);

	return -1;
}

int volumeUltimaMusicaGuloso(PCasoTeste casoTeste) {
	//não existe algoritmo guloso ótimo para o problema
	return -1;
}


/**
 * Verifica se a lista de casos está vazia
 * L -> estrutura ListaCasos
 */
int isListaCasosVazia(ListaCasos L) {
	return (L.Primeiro->prox == NULL);
}

/**
 * Aloca uma lista encadeada de casos
 * L -> estrutura ListaCaso
 */
void criarListaCasos(ListaCasos *L) {
	L->Primeiro = (PCasoTeste)malloc(sizeof(CasoTeste));
	L->Ultimo = (PCasoTeste)malloc(sizeof(CasoTeste));
	L->Primeiro->prox = NULL;
	L->Ultimo->prox = NULL;
}

/**
 * Insere a referência para um item na lista encadeada
 * L -> lista encadeada
 * P -> ponteiro para o item a ser inserido
 */
void inserirPonteiroCasoTeste(ListaCasos *L, PCasoTeste P) {
	if(isListaCasosVazia(*L))
		L->Primeiro->prox = P;
	else
	{
		L->Ultimo->prox->prox = P;
	}
	L->Ultimo->prox = P;
	P->prox = NULL;
}

/**
 * Insere um conjunto de dados para teste que forma um caso de teste
 * na lista encadeada de casos
 * numMusicas -> número de músicas que serão tocadas
 * volumeInicial -> volume da primeira musica a ser tocada
 * volumeLimite ->  volume máximo q as músicas podem atingir
 * variacoes -> variações de volume durante o show
 */
void inserirCasoTeste(ListaCasos *L, int numMusicas, int volumeInicial, int volumeLimite, int *variacoes) {

	PCasoTeste P = (PCasoTeste)malloc(sizeof(CasoTeste));
	ItemCasoTeste item;
	item.numMusicas = numMusicas;
	item.volumeInicial = volumeInicial;
	item.volumeLimite = volumeLimite;
	item.variacoes = variacoes;

	P->itemCasoTeste = item;

	inserirPonteiroCasoTeste(L,P);

}

/**
 * Imprime os dados da lista encadeada de casos
 */
void imprimirCasosTeste(ListaCasos L) {

	PCasoTeste aux = L.Primeiro->prox;
	while (aux != NULL)
	{
		printf("\nCaso de Teste ");
		printf("\nN. musicas: %d, inicio: %d, limite %d\nVariações: ", aux->itemCasoTeste.numMusicas, aux->itemCasoTeste.volumeInicial, aux->itemCasoTeste.volumeLimite);
		int i;
		for (i = 0; i < aux->itemCasoTeste.numMusicas - 1; i++)
			printf("%d,", aux->itemCasoTeste.variacoes[i]);
		aux = aux->prox;
	}
}

/**
 * Libera a memória alocada pela lista encadeada de casos
 */
ListaCasos *liberaCasosTeste(ListaCasos L) {

	PCasoTeste p = L.Primeiro->prox;
	while (p != NULL) {
		PCasoTeste t = p->prox;
		free(p->itemCasoTeste.variacoes);
		free(p);
		p = t;
	}

	return (NULL);
}
